package com.leetcode;

import com.study.common.ListNode;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-11-17 11:54
 * @version: 1.0
 * @description: 回文链表
 **/
public class IsPalindrome {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1, null);
        ListNode node2 = new ListNode(2, node1);
        ListNode node3 = new ListNode(2, node2);
        ListNode node4 = new ListNode(1, node3);
        System.out.println(isPalindrome(node4));

    }

    public static boolean isPalindrome(ListNode head) {
        //找数组中间位置
        ListNode slow = head,fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        // 如果链表是奇数，则slow再向下移动一位
        if(fast != null){
            slow = slow.next;
        }
        slow = reverse(slow);
        fast = head;
        while(slow != null){
            if(fast.value == slow.value){
                fast = fast.next;
                slow = slow.next;
            }else{
                return false;
            }
        }
        return true;
    }
    public static ListNode reverse(ListNode head) {
        ListNode prev = null,next,curr = head;
        while (curr != null){
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}
